package SwordOffer2;

public class day4_4 {
    /*
    * 1.计算二维数组的前缀和，保存在二维数组sums中
    * 2.根据(row1，col1)(row2，col2)之间的关系计算和
    * */

    int[][] sums;
    public day4_4(int[][] matrix) {
        int sum = 0;
        sums = new int[matrix.length][matrix[0].length];
        for (int i = 0; i < matrix.length; i++) {
            sum += matrix[i][0];
            sums[i][0] = sum;
        }
        sum = 0;
        for (int i = 0; i < matrix[0].length; i++) {
            sum += matrix[0][i];
            sums[0][i] = sum;
        }
        for (int i = 1; i < matrix.length; i++) {
            for (int j = 1; j < matrix[0].length; j++) {
                sums[i][j] = sums[i - 1][j] + sums[i][j - 1] - sums[i - 1][j - 1] + matrix[i][j];
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        int res = 0;
        if (row1 == 0 && col1 == 0) {
            res = sums[row2][col2];
        } else if (row1 == 0) {
            res = sums[row2][col2] - sums[row2][col1 - 1];
        } else if (col1 == 0) {
            res = sums[row2][col2] - sums[row1 - 1][col2];
        } else {
            //System.out.println("jin");
            res = sums[row2][col2] - sums[row2][col1 - 1] - sums[row1 - 1][col2] + sums[row1 - 1][col1 - 1];
        }
        return res;
    }
}
